import random;


def getMaxCircle(pNum):
    
    ans = 1
    vis = [0]*100
    for i in  range(100):
        if 0 == vis[i]:
            cnt = 0
            j = i
            while(0 == vis[j]):
                vis[j] = 1
                cnt += 1
                j = pNum[j]
        
            ans = max(ans, cnt) 
    
    return ans
    

def HunPrisoners(n):
    
    
    failure_cnt = 0
    for i in range(n):
        pNum = list(range(100))
        
        j = 99
        while j > 0:
            kth = random.randint(0, j)
            pNum[kth], pNum[j] = pNum[j],pNum[kth]
            j -= 1

        if getMaxCircle(pNum) > 50:
            failure_cnt += 1
    
    return 1 - (failure_cnt / n)
            

if __name__ == "__main__":
   
   n = 100
   while n < 10000000:
       print("repeate %d's possibility: %lf"%(n, HunPrisoners(n)))
       n *= 10